package com.xy6.algo.dynamic;

import java.util.Arrays;

/**
 * 数字三角形
 * <pre>
 * 北大POJ1163
 * 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
 * 路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 
 * 三角形的行数大于1小于等于100，数字为 0 - 99
 *  输入格式：
 * 5      //表示三角形的行数    接下来输入三角形
 * 7
 * 3   8
 * 8   1   0
 * 2   7   4   4
 * 4   5   2   6   5
 * 
 * 法一：
 * 性能：时间效率：O(n^2)，空间效率：n(n+1)/2 * 2 + C
 * 定义一个n维数组a，保存三角形各位置的值；
 * 定义一个n维数组b，保存从顶点到三角形各位置最大路径；
 * 遍历三角形层数从1到n，当前元素为i，则a数组在当前层元素个数为i；
 * 遍历当前层元素从1到i，当前元素为j，b数组在当前元素的值为：
 * max(左上元素值，正上元素值)+当前元素值，即b[i][j]=max(b[i-1][j-1], b[i-1][j]) + a[i][j]
 * 三角形规则：从上向下走，只能左下或者右下。在数组中表示，某一位置(i,j)向下走，只能右下(i+1,j+1)或者向下(i+1,j)。
 * 某一个位置(i,j)，其上一个位置，只能左上(i-1,j-1)或者向上(i-1,j)。
 * 遍历当前元素j后，得到从顶点到当前位置(i,j)的最大路径b[i][j]，继续遍历当前层下一个元素；
 * 遍历当前层i后，得到从顶点i到当前层各元素的最大路径b[i]，继续遍历下一层元素，直至遍历完最后一层n的元素；
 * 遍历b集合最后一层元素b[n]，找到最大值，即从顶点到底边的最大路径。
 * 
 * 状态转换方程：
 * b[i][j]=max(b[i-1][j-1], b[i-1][j]) + a[i][j] （i>=1 && i<=n）
 * i：三角形行号，j：三角形列号
 * max=max(b[n])
 * 
 * 
 * 法二：
 * 性能：时间效率：O(n^2)，空间效率：n(n+1)/2 + n + C
 * 定义一个n维数组a，保存三角形各位置的值；
 * 定义一个一维数组b，长度为n，保存从顶点到当前层各元素最大路径；
 * 遍历三角形层数从1到n，当前元素为i，则a数组在当前层元素个数为i；
 * 遍历当前层元素从i到1（注意：从后向前遍历，而非从前向后，避免修改b的元素后，影响下一个元素的计算），
 * 当前元素为j，b数组在当前元素的值为：
 * max(b的当前位置元素值，b的左元素值)+a的当前元素值，即b[j]=max(b[j-1], b[j]) + a[i][j]
 * 遍历当前元素j后，得到从顶点到当前位置(i,j)的最大路径b[i][j]，继续遍历当前层下一个元素；
 * 遍历当前层i后，得到从顶点i到当前层各元素的最大路径b[i]，继续遍历下一层元素，直至遍历完最后一层n的元素；
 * 遍历b集合，找到最大值，即从顶点到底边的最大路径。
 * 
 * 状态转换方程：
 * b[j]=max(b[j-1], b[j]) + a[i][j]) （i>=1 && i<=n）
 * i：三角形行号，j：三角形列号
 * max=max(b)
 * 
 * </pre>
 * 
 * @author zhang
 * @since 2017-11-01
 */
public class DigitTriangle {

	/**
	 * 计算从顶点到底边的最大路径和
	 * 
	 * @param a
	 * @return
	 */
	public static int calc(int a[][]){
		int n = a.length;
		int b[][] = new int[n][];
		// 计算每个位置累计值
		for(int i=0; i<n; i++){
			b[i] = new int[i + 1];
			for(int j=0; j<=i; j++){
				b[i][j] = max(b, i - 1, j, i - 1, j - 1) + a[i][j];
				System.out.print(String.format("%d ", b[i][j]));
			}
			System.out.println();
		}
		// 遍历最后一行元素
		int max = b[n-1][0];
		for (int i = 1; i < n; i++) {
			if(b[n-1][i] > max){
				max = b[n-1][i];
			}
		}
		return max;
	}
	
	/**
	 * 查找数组中两个元素最大值
	 * 
	 * @param a
	 * @param x1
	 * @param y1
	 * @param x2
	 * @param y2
	 * @return
	 */
	private static int max(int a[][], int x1, int y1, int x2, int y2){
		int num1 = 0;
		if(x1 >= 0 && y1 >= 0 && x1 < a.length && y1 < a[x1].length){
			num1 = a[x1][y1];
		}
		int num2 = 0;
		if(x2 >= 0 && y2 >= 0 && x2 < a.length && y2 < a[x1].length){
			num2 = a[x2][y2];
		}
		
		return num1 > num2 ? num1 : num2;
	}
	
	/**
	 * 计算从顶点到底边的最大路径和
	 * 
	 * @param a
	 * @return
	 */
	public static int calc2(int a[][]){
		int n = a.length;
		int b[] = new int[n];
		// 计算每个位置累计值
		for(int i=0; i<n; i++){
			for (int j = i; j >= 0; j--) {
				b[j] = max2(b, j, j-1) + a[i][j];
			}
			System.out.println("b:" + Arrays.toString(b));
		}
		// 遍历最后一行元素
		int max = b[0];
		for (int i = 1; i < n; i++) {
			if(b[i] > max){
				max = b[i];
			}
		}
		return max;
	}
	
	private static int max2(int a[], int x, int y){
		int num1 = 0;
		if(x >= 0 && x < a.length){
			num1 = a[x];
		}
		int num2 = 0;
		if(y >= 0 && y < a.length){
			num2 = a[y];
		}
		return num1 > num2 ? num1 : num2;
	}
}
